/*
 * =====================================================================================
 *
 *       Filename:  bstree.h
 *
 *    Description:  二叉搜索树
 *
 *        Version:  1.0
 *        Created:  2011-11-5 22:06:44
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */
#ifndef _BSTREE_H_
#define _BSTREE_H_

#include <functional>
#include <iostream>

struct _bs_tree_node_base {
    typedef _bs_tree_node_base *base_ptr;
    base_ptr parent;
    base_ptr left;
    base_ptr right;
    size_t   count;

    static base_ptr minmum(base_ptr x) {
        while (x->left) {
            x = x->left;
        }

        return x;
    }

    static base_ptr maxmum(base_ptr x) {
        while (x->right) {
            x = x->right;
        }

        return x;
    }

    static void _rotate_left(base_ptr x) {
        if (x->right == NULL) {
            return;
        }

        base_ptr root = x->right;

        if (x->right->left != NULL) {
            x->right->left->parent = x;
        }

        x->right = x->right->left;
        root->left = x;
        x->parent = root;
    }

    static void _rotate_right(base_ptr x) {
        if (x->left == NULL) {
            return ;
        }

        base_ptr root = x->left;

        if (x->left->right != NULL) {
            x->left->right->parent = x;
        }

        x->left = x->left->right;
        root->right = x;
        x->parent = root;
    }
};

template <class Value>
struct _bs_tree_node : public _bs_tree_node_base {
    _bs_tree_node_base *link_type;
    Value value_field;
};

template <class T>
struct identity : public std::unary_function<T, T> {
    const T &operator()(const T &x) const {
        return x;
    }
};

struct _bs_tree_base_iterator {
    typedef _bs_tree_node_base::base_ptr base_ptr;
    typedef ptrdiff_t difference_type;
    base_ptr node;

    //计算节点的后继
    void increment(void) {
        if (node->right != NULL) {
            node = node->right;

            while (node->left != NULL) {
                node = node->left;
            }
        } else {
            base_ptr y = node->parent;

            while (node == y->right) {
                node = y;
                y = y->parent;
            }

            //如果节点没有后继，则节点的后继为header
            if (node->right != y) {
                node = y;
            }
        }
    }

    //计算节点的前驱
    void decrement(void) {
        if (node->left != NULL) {
            node = node->left;

            while (node->left != NULL) {
                node = node->left;
            }
        } else {
            base_ptr y = node->parent;

            while (node == y->left) {
                node = y;
                y = y->parent;
            }

            //如果节点没有前驱，则节点的前驱为header
            if (node->left != y) {
                node = y;
            }
        }
    }
};

template <class Value, class Ref, class Ptr>
struct _bs_tree_iterator : public _bs_tree_base_iterator {
    typedef Value value_type;
    typedef Ref reference;
    typedef Ptr pointer;
    typedef _bs_tree_iterator<Value, Value &, Value *> iterator;
    typedef _bs_tree_iterator<Value, const Value &, const Value *> const_iterator;
    typedef _bs_tree_iterator<Value, Ref, Ptr> self;
    typedef _bs_tree_node<Value>* link_type;

    _bs_tree_iterator(void) {}
    _bs_tree_iterator(link_type x) {
        node = x;
    }
    _bs_tree_iterator(const iterator &it) {
        node = it.node;
    }

    reference operator*(void) const {
        return link_type(node)->value_field;
    }
    pointer operator->(void) const {
        return &(operator*());
    }
    self &operator++(void) {
        increment();
        return *this;
    }
    self operator++(int) {
        self tmp = *this;
        increment();
        return tmp;
    }
    self &operator--(void) {
        decrement();
        return *this;
    }
    self operator--(int) {
        self tmp = *this;
        decrement();
        return tmp;
    }
    bool operator==(const iterator &it) const {
        return node == it.node;
    }
    bool operator!=(const iterator &it) const {
        return node != it.node;
    }
};


template <class Key, class Value, class KeyOfValue>
class bs_tree
{
protected:
    typedef void *void_pointer;
    typedef _bs_tree_node_base *base_ptr;
    typedef _bs_tree_node<Value> bs_tree_node;

public:
    typedef Key key_type;
    typedef Value value_type;
    typedef value_type *pointer;
    typedef const value_type *const_pointer;
    typedef value_type &reference;
    typedef const value_type &const_reference;
    typedef bs_tree_node *link_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

protected:
    link_type create_node(const value_type &x) {
        link_type tmp = new bs_tree_node();
        tmp->value_field = x;
        tmp->parent = NULL;
        tmp->left = NULL;
        tmp->right = NULL;
        tmp->count = 1;
        return tmp;
    }

    void destory_node(link_type p) {
        delete p;
        p = NULL;
    }

protected:
    link_type header;

    link_type &root(void) const {
        return (link_type &)header->parent;
    }
    link_type &leftmost(void) const {
        return (link_type &)header->left;
    }
    link_type &rightmost(void) const {
        return (link_type &)header->right;
    }

    static link_type &parent(link_type x) {
        return (link_type &)x->parent;
    }
    static link_type &left(link_type x) {
        return (link_type &)x->left;
    }
    static link_type &right(link_type x) {
        return (link_type &)x->right;
    }
    static difference_type &count(link_type x) {
        return (difference_type &)x->count;
    }
    static reference value(link_type x) {
        return x->value_field;
    }
    static const Key &key(link_type x) {
        return KeyOfValue()(value(x));
    }

    static link_type minmum(link_type x) {
        return (link_type)bs_tree_node::minmum(x);
    }
    static link_type maxmum(link_type x) {
        return (link_type)bs_tree_node::maxmum(x);
    }

public:
    typedef _bs_tree_iterator<value_type, reference, pointer> iterator;

private:
    void init(void) {
        header = new bs_tree_node();
    }

    /*
    bs_tree<Key, Value, KeyOfValue, Compare>& operator =(const bs_tree<Key, Value, KeyOfValue, Compare>& x) {
        if (this == &x) {
            return *this;
        }

        link_type px = x.root();
        link_type ps = root();

        while (px->left() || px->right()) {
            if (px->left())  {
                left(ps) = create(value(left(px)));
                px = left(px);
                ps = left(ps);
            }
            if (right(px)) {
                right(ps) = create(value(right(px)));
                px =
            }
        }
    }
    */

    void _visit(link_type x) const {
        if (x) {
            std::cout << x->value_field;
        }
    }

    void _inorder(link_type x) const {
        if (x == NULL) {
            return;
        }

        _inorder(left(x));
        _visit(x);
        std::cout << " ";
        _inorder(right(x));
    }

    int _depth(link_type x) const {
        if (x == NULL) {
            return -1;
        }

        return std::max(_depth(left(x)), _depth(right(x))) + 1;
    }

    void _level_order(link_type x, int d) const {
        if (x == NULL || d < 0) {
            return;
        }

        if (d == 0) {
            _visit(x);
            std::cout << " ";
            return ;
        } else {
            _level_order(left(x), d - 1);
            _level_order(right(x), d - 1);
        }
    }

    void _update_count(link_type &x) {
        count(x) = ((left(x) == NULL) ? 0 : count(left(x))) + ((right(x) == NULL) ? 0 : count(right(x))) + 1;
    }

    iterator _insert(link_type y, const Value &v) {
        link_type x = create_node(v);

        if (y == header) {
            root() = x;
            leftmost() = x;
            rightmost() = x;
        } else if (KeyOfValue()(v) <= key(y)) {
            left(y) = x;

            if (leftmost() == y) {
                leftmost() = x;
            }
        } else {
            right(y) = x;

            if (rightmost() == y) {
                rightmost() = y;
            }
        }

        x->parent = y;
        x->left = NULL;
        x->right = NULL;

        while (y != header) {
            count(y) += 1;
            y = parent(y);
        }

        return iterator(x);
    }

    void _insertHead(link_type &h, const value_type &v) {
        if (h == NULL) {
            h = create_node(v);
            return;
        }

        if (KeyOfValue()(v) < key(h)) {
            _insertHead(left(h), v);
            _update_count(h);

            if (leftmost() == h) {
                leftmost() = left(h);
            }

            _bs_tree_rotate_right(h, root());
        } else {
            _insertHead(right(h), v);
            _update_count(h);

            if (rightmost() == h) {
                rightmost() = right(h);
            }

            _bs_tree_rotate_left(h, root());
        }

    }
    {
    iterator _insertRandom(link_type &h, const value_type &v) {
        if (h == NULL) {
            h = create_node(v);
            return ;
        }
        if (rand() < RAND_MAX/(count(h)+1)) {
            _insertHead(h, v);
            return;
        }
        if (KeyOfValue()(v) < key(h)) {
            _insert(left(h), v);
        } else {
            _insert(right(h), v);
        }
    }

    void _bs_tree_rotate_left(link_type x, link_type &root) {
        link_type y = right(x);
        right(x) = left(y);

        if (left(y) != NULL) {
            parent(left(y)) = x;
        }

        left(y) = x;
        parent(y) = parent(x);

        if (x == root) {
            root = y;
        } else if (x == left(parent(x))) {
            left(parent(x)) = y;
        } else {
            right(parent(x)) = y;
        }

        parent(x) = y;
        _update_count(x);
        _update_count(y);
    }

    void _bs_tree_rotate_right(link_type x, link_type &root) {
        link_type y = left(x);
        left(x) = right(y);

        if (right(y) != NULL) {
            parent(right(y)) = x;
        }

        right(y) = x;
        parent(y) = parent(x);

        if (x == root) {
            root = y;
        } else if (x == left(parent(x))) {
            left(parent(x)) = y;
        } else {
            right(parent(x)) = y;
        }

        parent(x) = y;
        _update_count(x);
        _update_count(y);
    }


public:
    bs_tree(void) {
        init();
    }
    ~bs_tree(void) {
        //clear();
        delete header;
    }

public:
    iterator begin(void) {
        return leftmost();
    }

    iterator end(void) {
        return header;
    }

    bool empty(void) const {
        return root() == NULL;
    }

    void inorder(void) const {
        _inorder(root());
    }

    int depth(void) const {
        return _depth(root());
    }

    void level_order(void) {
        int d = depth();

        for (int i = 0; i <= d; ++i) {
            _level_order(root(), i);
            std::cout << std::endl;
        }
    }

    iterator insertBottom(const value_type &v) {
        link_type y = header;
        link_type x = root();

        while (x) {
            if (KeyOfValue()(v) < key(x)) {
                y = x, x = left(x);
            } else if (KeyOfValue()(v) > key(x)) {
                y = x, x = right(x);
            } else {
                return _insert(parent(x), v);
            }
        }

        return _insert(y, v);
    }

    iterator insertHead(const value_type &v) {
        if (root() == NULL) {
            link_type x = create_node(v);
            root() = x;
            parent(x) = header;
            leftmost() = x;
            rightmost() = x;
        } else {
            _insertHead(root(), v);
        }

        return iterator(root());
    }

    void erase(const key_type &x_) {
        iterator xt = find(x_);

        if (xt == end()) {
            return ;
        }

        link_type x = (link_type)xt.node;

        if (left(x) != NULL && right(x) != NULL) {
            link_type succ = (link_type)((++xt).node);
            std::swap(value(succ), value(x));
            x = succ;
        }

        //更新父节点的count域
        link_type y = parent(x);

        while (y != header) {
            count(y) += -1;
            y = parent(y);
        }

        if (left(x) != NULL) {
            if (left(parent(x)) == x) {
                left(parent(x)) = left(x);
            } else {
                right(parent(x)) = left(x);
            }

            parent(left(x)) = parent(x);
        } else if (right(x) != NULL) {
            if (left(parent(x)) == x) {
                left(parent(x)) = right(x);
            } else {
                right(parent(x)) = right(x);
            }

            parent(right(x)) = parent(x);
        } else {
            if (left(parent(x)) == x) {
                left(parent(x)) = NULL;
            }

            if (right(parent(x)) == x) {
                right(parent(x)) = NULL;
            }

            if (leftmost() == x) {
                leftmost() = parent(x);
            }

            if (rightmost() == x) {
                rightmost() = parent(x);
            }
        }

        destory_node(x);
    }

    iterator find(const key_type &v) {
        link_type x = root();

        while (x) {
            if (KeyOfValue()(v) < key(x)) {
                x = left(x);
            } else if (KeyOfValue()(v) > key(x)) {
                x = right(x);
            } else {
                return x;
            }
        }

        return iterator(x);
    }

    iterator select(int k) {
        link_type x = root();

        while (x != NULL) {
            int t = (left(x) == NULL) ? 0 : count(left(x));

            if (t >= k) {
                x = left(x);
            } else if (t + 1 < k) {
                k = k - (t + 1);
                x = right(x);
            } else {
                return iterator(x);
            }
        }

        return end();
    }

    //void join(bs_tree<Key, Value, KeyOfValue, Compare> &t) {
    //
    //}
};

#endif
